#ifndef STX_ALGORITHM_PARTIAL_SORT_HPP
#define STX_ALGORITHM_PARTIAL_SORT_HPP

#include <stx/algorithm/common.hpp>
#include <stx/algorithm/swap.hpp>
#include <stx/algorithm/make_heap.hpp>
#include <stx/algorithm/push_heap.hpp>
#include <stx/algorithm/sort_heap.hpp>

namespace stx {

template <class Compare, class RandomAccessIterator>
inline void
partial_sort_impl(
    RandomAccessIterator first,
    RandomAccessIterator middle,
    RandomAccessIterator last,
    Compare comp)
{
    make_heap_impl<Compare>(first, middle, comp);
    typename std::iterator_traits<RandomAccessIterator>::difference_type len = middle - first;
    for (RandomAccessIterator i = middle; i != last; ++i) {
        if (comp(*i, *first)) {
            swap(*i, *first);
            push_heap_front<Compare>(first, middle, comp, len);
        }
    }
    sort_heap_impl<Compare>(first, middle, comp);
}

template <class RandomAccessIterator, class Compare>
inline void
partial_sort(
    RandomAccessIterator first,
    RandomAccessIterator middle,
    RandomAccessIterator last,
    Compare comp)
{
    typedef typename add_lvalue_reference<Compare>::type comp_ref;
    partial_sort_impl<comp_ref>(first, middle, last, comp);
}

template <class RandomAccessIterator>
inline void
partial_sort(
    RandomAccessIterator first,
    RandomAccessIterator middle,
    RandomAccessIterator last)
{
    stx::partial_sort(
        first,
        middle,
        last,
        stx::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
}

} // namespace stx

#endif // STX_ALGORITHM_PARTIAL_SORT_HPP
